1. Field of the Invention
The present invention relates generally to switching networks and more specifically to an apparatus and a method for queuing and scheduling asynchronous transfer mode (ATM) cells in an ATM switch.
2. Description of the Related Art
ATM networks and switches support a mixture of traffic, including bursty traffic. By its nature, bursty traffic requires high bit rates for part of the time and little or no bit rate for the rest of the time. In order to efficiently use the bit rate available in a network, it is necessary to allocate a connection a lower bit rate than its peak bit rate such that the total peak bit rate of all the connections may be greater than the bit rate of the network links.
To support this situation, an ATM multiplexer requires large buffers at the input of the switch to buffer cells when they arrive at the multiplexer and cannot be transmitted across it, and buffers at the output of the switch, so that traffic may be shaped, whereby the profile of the traffic is altered before transmission from the switch. Such a switch with large buffers is termed a large buffered switch.
In an ATM network, a user, who wishes to set up a connection-orientated virtual channel connection in a quality of service category where statistical gain is required, will have to negotiate with the network at least three traffic parameters. These parameters will include the peak cell rate, the sustainable cell rate and some measure of the maximum burst size. Output buffers are therefore required to store cells so that they are transmitted at their sustainable cell rate but not above their peak cell rate. This process must be completed for a plurality of ATM virtual channel connections.
German patent application number 93120828.4 discusses an egress shaping algorithm. If the sum of the sustainable cell rates for connections accepted for an egress network link can be handled by the bit rate available for statistically multiplexed services on a network link, the egress scheduler/shaper disclosed in the application referred to above can guarantee a minimum service rate equal to the sustainable cell rates for each connection on a link using a simple resource allocation procedure which can provide high levels of statistical gain with bounded buffer sizes.
Referring to FIG. 1, this prior art block diagram shows how ATM cells 2 enter the system on an input line. This line comes from the part of the device which has multiplexed all the cells destined for this egress queue. The virtual path identifier/virtual channel identifier VPI/VCI of the cell is used to obtain the maximum allowed delay, Dmax, in order to maintain the sustainable cell rate as the minimum service rate for that virtual channel connection. The value Dmax is then fed into a cell buffer manager 4 from a leaky bucket manager 6. The cell buffer manager 4 schedules the cell for transmission via a calendar mechanism. The output line transfers cells from the calendar, however, they may be multiplexed together with other cells before being transmitted onto the network egress link.
The known calendar mechanism used is shown in FIG. 2, in which the following abbreviations are used. FLT is the Free List Tail. FLH is the Free List Head. CET is the Calendar Entry Tail. CEH is the Calendar Entry Head. OLT is the Output List Tail, and OLH is the Output List Head. The constituent components of the cell buffer manager are the cell memory, the calendar and a series of pointers. When a cell arrives at the cell buffer manager, a free cell location is taken from the head of the free cell list and the cell is copied to this location. The cell is then scheduled onto the calendar at time T+Dmax (modulo N.sub.CA) where time T is the current time and N.sub.CA is the size of the calendar. If another cell is scheduled for the same time slot, then it is added to the front of the queue within the calendar time slot.
There are two output time pointers, a real time pointer T, and a read pointer RP which can move ahead of the real time pointer. While the RP and T pointers point to the same time slot, the complete linked list of cells connected to a time slot is transferred to the output queue. If the RP pointer moves ahead of the T pointer, then when it finds a time slot with cells in it, the cells are moved to the output queue one at a time so that there is never more than one cell in the output buffer. The reason for this is that the RP pointer is moving ahead of the time when the cell must be transmitted from the output calendar, denoted by pointer T. If a cell arrives at the output calendar and it requires that it be scheduled immediately at time T, the cell must be transferred to the output queue directly and should be transmitted from the output queue without delay. For this reason the output queue must never have more than one cell in it when the pointer RP is ahead of the real time pointer T. However, in this situation, pointer RP may remain at its position to a cell slot ahead of pointer T.
If a cell arrives at the calendar and requires to be scheduled between pointers T and RP, the cell is scheduled, but also the pointer RP is returned to the time slot position of this newly scheduled cell. After processing it, the pointer RP then searches through the calendar again for non-empty time slots. The reason for this is that if the cell arrival rate is greater than the transmission rate, many cells may arrive at the calendar and require scheduling between pointers RP and T. Simply transferring them to the output port will leave cells with later departure times being transmitted before cells with immediate departure times. The pointer RP must always be pointing to the closest time slot to pointer T with cells in it.
In the situation where the pointer RP is ahead of the pointer T, if the load on the port increases, the linked lists associated with each time slot will increase in length and eventually the real time pointer T will "catch up" with the read pointer RP.
Thus it is possible for the read pointer to get ahead of the current time T but never behind. Hence, this algorithm will guarantee the sustainable cell rate for a given virtual channel connection but has no limit on the peak cell rate.